#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/

/*  算法10-13：二路归并求逆序对减量 TwoWayInversionCount(a,l,m,r) */
int TwoWayInversionCount(ElemSet *a, int l, int m, int r) {
    int i, j, k, count;
    ElemSet *t;

    t = (ElemSet *)malloc(sizeof(ElemSet) * (r - l + 1)); /* 创建临时数组 */
    i = l;
    j = m + 1;
    k = 0;
    count = 0;
    while (i <= m || j <= r) {
        if (j > r || (i <= m && a[i] <= a[j])) {
            t[k] = a[i]; /* 将a[i]添加至t末尾 */
            i++;
        } else {
            t[k] = a[j]; /* 将a[j]添加至t末尾 */
            j++;
            count += (m - i + 1);
        }
        k++;
    }
    for (i = l; i <= r; i++) { /* 将归并后的有序序列t复制回a中 */
        a[i] = t[i - l];
    }
    return count;
}
/* 算法10-13 结束 */

/*  算法10-14：归并排序兼求逆序对数量 InversionCount(a,l,r) */
int InversionCount(ElemSet *a, int l, int r) {
    int m, count;

    count = 0;
    if (l < r) { /* 序列中有至少两个元素待排 */
        m = (l + r) >> 1;
        count += InversionCount(a, l, m);
        count += InversionCount(a, m + 1, r);
        count += TwoWayInversionCount(a, l, m, r);
    }
    return count;
}
/* 算法10-14 结束 */

int main(void) {
    ElemSet *a; /* 数组a的下标从0开始 */
    int n, i;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("count = %d\n", InversionCount(a, 0, n - 1));
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}